#define _CRT_SECURE_NO_WARNINGS

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum = 0;
        for (int i = 0; i < stones.size(); i++)
            sum += stones[i];
        vector<int> dp(1501, 0);
        for (int i = 0; i < stones.size(); i++)
        {
            for (int j = sum / 2; j >= stones[i]; j--)
            {
                dp[j] = max(dp[j], stones[i] + dp[j - stones[i]]);
            }
        }
        return sum - dp[sum / 2] - dp[sum / 2];
    }
};

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        for (int i = 0; i < nums.size(); i++)
            sum += nums[i];
        if ((sum + target) % 2 == 1 || sum < abs(target))
            return 0;
        int num = (sum + target) / 2;
        vector<int> dp(20001, 0);
        dp[0] = 1;
        for (int i = 0; i < nums.size(); i++)
        {
            for (int j = num; j >= nums[i]; j--)
            {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[num];
    }
};

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>>dp(m + 1, vector<int>(n + 1, 0));
        for (auto e : strs)
        {
            int num0 = 0, num1 = 0;
            for (auto f : e)
            {
                if (f == '0')
                    num0++;
                else
                    num1++;
            }
            for (int i = m; i >= num0; i--)
            {
                for (int j = n; j >= num1; j--)
                    dp[i][j] = max(dp[i][j], dp[i - num0][j - num1] + 1);
            }
        }
        return dp[m][n];
    }
};